This invention relates to a shared buffer control device which can be used in a packet or cell switching unit using buffers or in an input or output terminal module of an asynchronous switching network using buffers.
Information is increasingly transmitted using digital signals transmitted in the form of asynchronous data made up of packets or cells that are transmitted from their point of origin to their point of arrival via nodes at which a number of lines converge and from which a multiplicity of lines depart. A packet or a cell must be switched from an input line to at least one output line. This switching, which is effected under the control of a routing algorithm, is performed by switching units each of which comprises a plurality of inputs (n1 inputs) and a plurality of outputs (n2 outputs).
In some conventional switching units input data is stored in a buffer from which it is subsequently extracted to be transmitted to the output chosen by the routing algorithm.
The simplest version of a switching unit of the above kind includes an individual buffer for each of the n2 outputs, each item of input data being written into the buffer relating to the output chosen by the routing algorithm. However, to simplify these units it is known to use a single buffer called a xe2x80x9cshared bufferxe2x80x9d. In this case the switching unit typically includes an input multiplexer and an output demultiplexer and control means for controlling the buffer in particular.
The operation of a unit of the above kind is cyclic. Each cycle corresponds to writing into the shared buffer data received on each of the n1 inputs and to reading from the shared buffer data to be transmitted to each of the n2 outputs. Each cycle is conventionally divided into a number of time slots during each of which a data block read operation and/or a data block write operation is/are effected. During a given time slot comprising both types of operation a data block received on a particular input is written and a data block to be transmitted to a given output is read but a read operation and a write operation at the same buffer location must be effected at different times.
The duration of a cycle is conditioned by three parameters, namely the binary bit rate at the inputs and outputs of the switching unit, the number of bits of a data block processed in parallel, and the number of inputs and outputs of the switching unit. Although it is desirable to increase the capacity (n1xc3x97n2) of the switching unit, the duration of a cycle is reduced when the inputs/outputs are at a high bit rate and it is not possible to increase the size of a data block processed in parallel beyond certain limits of complexity.
In broadband applications the need to increase the number of inputs and outputs reduces the duration of the time slots and therefore the time allocated to each operation to write or to read the shared buffer. This can not only lead to prohibitive additional costs but also run up against performance limits of the technology in terms of memory access time.
European Patent Application No. EP 0 700 187 (Mitsubishi) describes a shared buffer control device that includes a plurality of sub-buffers. The shared sub-buffers are controlled so that during at least some time slots writing an input data block and extracting a data block to an output can be effected simultaneously in separate shared sub-buffers, selecting the shared sub-buffers for reading taking priority over selecting the shared sub-buffer for writing.
In this way, for each read operation, as for each write operation, all of the time slot is available whereas with a switching unit of the previous prior art type a time slot has to be shared in order to effect the two types of operation consecutively. The set of shared sub-buffers, all of which have the same capacity and are identical to each other, constitutes a virtual shared buffer equivalent to a single shared buffer of a prior art switching unit.
The prior art control device includes a shared buffer control unit for controlling an input switch and selecting the shared sub-buffer into which a received cell is written. The unit reads a plurality of cells in a plurality of shared sub-buffers during a time cycle corresponding to that of a cell and controls an output switch to transmit each cell read to a selected output. The control device updates a sub-buffer access table having a first dimension representing the number of sub-buffers and a second dimension representing the number of time slots in a time cycle corresponding to that of a cell.
Arbitration between write access and read access to the sub-buffers is controlled in parallel for all access time slots (n1 wrote access and n2 read access for a switching unit with n1 inputs and n2 outputs) in a time cycle corresponding to that of a cell.
The control device is complex and the aim of the present invention is to propose a simpler control device.
In accordance with the invention, a control device for a shared buffer comprising a plurality of shared sub-buffers, a write selector circuit for writing therein data blocks from inputs, and a read selector circuit for reading said data blocks therein afterwards and directing them to at least one output; said two selector circuits including arbitration means for writing and reading data blocks:
in accordance with periodic cycles, each cycle including time slots during each of which a data block received at an input can be written into one of said shared sub-buffers and during which a data block previously written can be read and sent to a particular output;
simultaneously, at least during some of said time slots, writing a data block from an input and reading a data block to be sent to an output in different shared sub-buffers; selecting a sub-buffer for reading taking priority over selecting the same sub-buffer for writing;
wherein said arbitration means include means for arbitrating a single write access vis a vis a single read access during each time slot.
This control device is simpler to produce because arbitration between sub-buffer write access and read access is managed serially, i.e. successively for each Individual time slot for access to a sub-buffer within a time cycle corresponding to that of a cell. It performs a single logic operation during each time slot to arbitrate a single write access relative to a single read access.
To control a device of the above kind it is necessary to take account of the fact that choosing the shared sub-buffer in which to write is limited not only by the availability of free locations in the various shared sub-buffers but also by the unavailability of access to the shared sub-buffer selected for reading, which takes priority. It is therefore necessary to know the number of the shared sub-buffer in which the data block to be read is stored in order to be able to select another shared sub-buffer in which an incoming data block can be stored; this selection is effected in accordance with the availability of free locations of the sub-buffers, for example.
Control must also allow for the risks of blocking during writing. Compared to a switching unit with a single shared buffer, a switching unit in accordance with the invention has an additional risk of blocking, which can occur when only the shared sub-buffer used for reading has free locations and all the other shared sub-buffers accessible for writing are entirely filled. The risk of blocking is an additional risk in that it does not exist in the conventional case of a single shared buffer (in which case it is always possible to write in the last free location, regardless of which one it is).
The additional possibility of blocking decreases as the number of shared sub-buffers increases. However, as increasing the number of buffers makes control more complex, it is in practice preferable to limit this number to a relatively low value.
In one preferred embodiment, the two selector circuits are such that, for each time slot, the choice of the sub-buffer for writing a data block depends on the state and/or the degree of filling of each of the shared sub-buffers.
To reduce the additional risk of blocking it is preferable to write the least heavily loaded shared sub-buffer.
However, this type of control does not entirely eliminate the additional risk of blocking. To eliminate it completely a sufficient capacity must be chosen for the shared sub-buffers. It can be shown that the probability of congestion of the equivalent virtual shared sub-buffer will be less than or equal to the probability of congestion of a unit with a single shared buffer of capacity S if the capacity Sxe2x80x2 of each shared sub-buffer is such that Sxe2x80x2xe2x89xa7S/(pxe2x88x921), p being the number of shared sub-buffers.
Another feature of the invention is that the access time allocated to the operations which update the chained lists in the buffers controlling free and/or occupied locations is, compared to a switching unit with a single shared buffer, increased in the same way as the access time allocated to the data block write and read operations is increased.